package com.eugenes.collections;

import com.eugenes.exceptions.MyIndexOutOfBoundsException;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public final class MyLinkedList<E> implements MyList<E>,
        MyStack<E>, MyQueue<E> {

    private int size;

    private int modificationsCount = Integer.MIN_VALUE;

    private Node<E> head;
    private Node<E> tail;

    public MyLinkedList() {}

    public MyLinkedList(Iterable<? extends E> c) {
        addAll(c);
    }

    private void checkIndex(int index, int lower, int upper) {
        if (index >= upper || index < lower) {
            throw new MyIndexOutOfBoundsException("Index out of bounds: " + index + ".");
        }
    }

    private Node<E> getNodeByIndex(int index) {
        assert (index >= 0 && index < size);

        if (index == size - 1) {
            return tail;
        }

        Node<E> result = head;
        while (index != 0) {
            --index;
            result = result.next;
        }

        return result;
    }

    @Override
    public void addAll(int index, Iterable<? extends E> c) {
        checkIndex(index, 0, size + 1);

        // create list with all elements from c
        Node<E> first = null;
        Node<E> last = null;

        int sizeC = 0;

        for (E element : c) {
            ++sizeC;

            Node<E> newNode = new Node(element);
            if (first == null) {
                first = last = newNode;
            } else {
                linkNodes(last, newNode);
                last = newNode;
            }
        }

        // find nodes to insert new list between them
        Node<E> pNode = null;
        Node<E> nNode = head;
        if (index == size) {
            pNode = tail;
            nNode = null;
        } else {
            while (index != 0) {
                --index;
                pNode = nNode;
                nNode = nNode.next;
            }
        }

        linkNodes(pNode, first);
        linkNodes(last, nNode);

        // restoring head and tail after insertion
        if (pNode == null) {
            head = first;
        }
        if (nNode == null) {
            tail = last;
        }

        size += sizeC;
        ++modificationsCount;
    }

    @Override
    public void addAll(Iterable<? extends E> c) {
        addAll(size, c);
    }

    @Override
    public void add(E element) {
        addAll(size, new Node(element));
    }

    @Override
    public void add(int index, E element) {
        addAll(index, new Node(element));
    }

    private void clearNode(Node<E> node) {
        node.item = null;
        node.prev = node.next = null;
    }

    @Override
    public void clear() {
        Node<E> curNode = head;

        while (curNode != null) {
            Node<E> nxt = curNode.next;
            clearNode(curNode);
            curNode = nxt;
        }

        head = tail = null;
        size = 0;
        ++modificationsCount;
    }

    @Override
    public E remove(int index) {
        checkIndex(index, 0, size);

        Node<E> node = getNodeByIndex(index);

        E result = node.item;
        linkNodes(node.prev, node.next);
        if (node.prev == null) {
            head = node.next;
        }
        if (node.next == null) {
            tail = node.prev;
        }
        clearNode(node);

        --size;
        ++modificationsCount;

        return result;
    }

    @Override
    public void set(int index, E element) {
        checkIndex(index, 0, size);

        Node<E> node = getNodeByIndex(index);
        node.item = element;

        ++modificationsCount;
    }

    @Override
    public E get(int index) {
        checkIndex(index, 0, size);

        Node<E> node = getNodeByIndex(index);
        return node.item;
    }

    @Override
    public int indexOf(Object element) {
        Node<E> curNode = head;
        int result = 0;
        while (curNode != null && !curNode.itemEquals(element)) {
            curNode = curNode.next;
            ++result;
        }
        return curNode == null ? -1 : result;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public Object[] toArray() {
        Object[] result = new Object[size];
        int index = 0;
        Node<E> curNode = head;
        while (curNode != null) {
            result[index++] = curNode.item;
            curNode = curNode.next;
        }
        return result;
    }

    @Override
    public Iterator<E> iterator() {
        return new ForwardIterator();
    }

    @Override
    public void push(E element) {
        add(element);
    }

    @Override
    public E pop() {
        E result = get(size - 1);
        removeLast();

        return result;
    }

    @Override
    public void offer(E element) {
        add(element);
    }

    @Override
    public E peek() {
        return get(0);
    }

    @Override
    public E poll() {
        E result = get(0);
        removeFirst();

        return result;
    }

    public void addFirst(E element) {
        addAll(0, new Node(element));
    }

    public void addLast(E element) {
        add(element);
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(size - 1);
    }

    public void removeFirst() {
        remove(0);
    }

    public void removeLast() {
        remove(size - 1);
    }

    public Iterator<E> descendingIterator() {
        return new BackwardIterator();
    }

    private static class Node<E> implements Iterable<E> {
        private Node<E> prev;
        private Node<E> next;
        private E item;

        public Node(E item) {
            this(null, null, item);
        }

        public Node(Node<E> prev, Node<E> next, E item) {
            this.prev = prev;
            this.next = next;
            this.item = item;
        }

        public boolean itemEquals(Object o) {
            return (o == null ? item == null : o.equals(item));
        }

        public Iterator<E> iterator() {
            return new Iterator<E>() {
                private boolean hasNext = true;

                @Override
                public boolean hasNext() {
                    return hasNext;
                }

                @Override
                public E next() {
                    if (!hasNext()) {
                        throw new NoSuchElementException("Node has only one element!");
                    }
                    hasNext = false;
                    return item;
                }

                @Override
                public void remove() {
                    throw new UnsupportedOperationException("Cannot remove from single node.");
                }
            };
        }
    }

    private void linkNodes(Node<E> prev, Node<E> next) {
        if (prev != null) {
            prev.next = next;
        }

        if (next != null) {
            next.prev = prev;
        }
    }

    private abstract class ListIterator implements Iterator<E> {
        protected Node<E> pNode;
        protected Node<E> nNode;

        private int lastModification;
        private boolean wasRemoved = true;

        protected ListIterator(Node<E> pNode, Node<E> nNode) {
            this.pNode = pNode;
            this.nNode = nNode;
            this.lastModification = modificationsCount;
        }

        protected abstract Node<E> nextNode(Node<E> node);
        protected abstract Node<E> prevNode(Node<E> node);

        protected void checkModification() {
            if (lastModification != modificationsCount) {
                throw new ConcurrentModificationException("List was modified after iterator had been created");
            }
        }

        protected void checkRemoved() {
            if (wasRemoved) {
                throw new IllegalStateException("Call next() method before removing element.");
            }
        }

        @Override
        public boolean hasNext() {
            return nNode != null;
        }

        @Override
        public E next() {
            checkModification();

            pNode = nNode;
            E result = nNode.item;
            nNode = nextNode(nNode);
            wasRemoved = false;

            return result;
        }

        @Override
        public void remove() {
            checkModification();
            checkRemoved();
            wasRemoved = true;

            Node<E> prev = prevNode(pNode);
            clearNode(pNode);
            linkNodes(prev, nNode);
            pNode = prev;

            if (pNode == null) {
                head = nNode;
            }
            if (nNode == null) {
                tail = pNode;
            }

            --size;
        }
    }

    private class ForwardIterator extends ListIterator {

        public ForwardIterator() {
            super(null, head);
        }

        @Override
        protected Node<E> prevNode(Node<E> node) {
            return node.prev;
        }

        @Override
        protected Node<E> nextNode(Node<E> node) {
            return node.next;
        }
    }

    private class BackwardIterator extends ListIterator {

        public BackwardIterator() {
            super(null, tail);
        }

        @Override
        protected Node<E> nextNode(Node<E> node) {
            return node.prev;
        }

        @Override
        protected Node<E> prevNode(Node<E> node) {
            return node.next;
        }
    }
}
